import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-08
 * Time: 22:17
 */
public class Solution {


    /**
     *  单调栈
     */
    public boolean find132pattern(int[] nums) {
        int len = nums.length;
        Stack<Integer> stack = new Stack<>();
        int k = Integer.MIN_VALUE; // k 记录出栈的最大值， k 如果有值的话，就说明栈中一定存在 比 k 大的值
        // 因为 k, 存储的是出栈的值，只有不符合单调栈的条件才会出栈，新进去的值 比 k 大，所以 K 要出来
        for (int i = len-1; i >= 0; i--) {
            // nums[i] < k， 就说明  (nums[i] < k < 栈中某个值) 满足条件
            // 并且 i < 栈中值的下标 < k的下标
            if (nums[i] < k) {
                return true;
            }
            // 单调栈
            while (!stack.isEmpty() && stack.peek() < nums[i]) {
                k = Math.max(stack.pop(), k);
            }
            stack.push(nums[i]);
        }
        return false;
    }
}
